<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>接雨水</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="接雨水">接雨水</h1>
<h1 id="1-lc-42-trapping-rain-water">1. LC 42 Trapping Rain Water</h1>
<ul>
<li><a href="https://leetcode.com/problems/trapping-rain-water/">https://leetcode.com/problems/trapping-rain-water/</a></li>
</ul>
<p>Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.</p>
<pre><code><code><div>Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
</div></code></code></pre>
<p>我的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trap</span><span class="hljs-params">(self, height: List[int])</span> -&gt; int:</span>
        n = len(height)
        <span class="hljs-keyword">if</span> n &lt;= <span class="hljs-number">2</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        left_max = height[<span class="hljs-number">0</span>]
        right_max = height[n<span class="hljs-number">-1</span>]
        ans = <span class="hljs-number">0</span>
        left = <span class="hljs-number">0</span>
        right = n - <span class="hljs-number">1</span>
        <span class="hljs-keyword">while</span> left &lt;= right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            
            <span class="hljs-keyword">if</span> left_max &lt; right_max:
                ans += left_max - height[left]
                left += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                ans += right_max -height[right]
                right -= <span class="hljs-number">1</span>
                
        <span class="hljs-keyword">return</span> ans

</div></code></pre>
<h1 id="2-lc-456-132-pattern">2. LC 456. 132 Pattern</h1>
<ul>
<li><a href="https://leetcode.com/problems/132-pattern/">https://leetcode.com/problems/132-pattern/</a></li>
</ul>
<p>Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i &lt; j &lt; k and nums[i] &lt; nums[k] &lt; nums[j].</p>
<p>Return true if there is a 132 pattern in nums, otherwise, return false.</p>
<p>Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?</p>
<pre><code><code><div>Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
</div></code></code></pre>
<p>我的解法O(n^2)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find132pattern</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; bool:</span>
        n = len(nums)
        <span class="hljs-keyword">if</span> n &lt; <span class="hljs-number">3</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        q1 = [nums[<span class="hljs-number">0</span>]]
        q2 = []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):

            <span class="hljs-keyword">if</span> q2:
                <span class="hljs-keyword">for</span> a, b <span class="hljs-keyword">in</span> q2:
                    <span class="hljs-keyword">if</span> a &lt; nums[i] &lt; b:
                        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
                    
            <span class="hljs-keyword">if</span> q1[<span class="hljs-number">0</span>] &lt; nums[i] &lt; q1[<span class="hljs-number">-1</span>]:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">elif</span> nums[i] &gt; q1[<span class="hljs-number">-1</span>]:
                q1.append(nums[i])
            <span class="hljs-keyword">elif</span> nums[i] &lt; q1[<span class="hljs-number">0</span>]:
                q2.append((q1[<span class="hljs-number">0</span>], q1[<span class="hljs-number">-1</span>]))
                q1 = [nums[i]]
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
    
</div></code></pre>
<p>官方答案解法O(n)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find132pattern</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; bool:</span>
        n = len(nums)
        <span class="hljs-keyword">if</span> n &lt; <span class="hljs-number">3</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        minv = [<span class="hljs-number">0</span>] * n
        minv[<span class="hljs-number">0</span>] = nums[<span class="hljs-number">0</span>]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
            <span class="hljs-comment"># 这里改成  minv[i] = min(minv[i-1], nums[i-1])  也没有问题。</span>
            <span class="hljs-comment"># minv[i] 可以有两种含义</span>
            <span class="hljs-comment"># (1) 表示到目前为止的最小值</span>
            <span class="hljs-comment"># (2) 表示到i的时候，左侧所有元素的最小值</span>
            <span class="hljs-comment"># 在本题里面，两个含义都能通过</span>
            minv[i] = min(minv[i<span class="hljs-number">-1</span>], nums[i])  
            
        q = []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            <span class="hljs-keyword">while</span> q <span class="hljs-keyword">and</span> q[<span class="hljs-number">-1</span>] &lt;= minv[i]:
                q.pop()
            <span class="hljs-keyword">if</span> q <span class="hljs-keyword">and</span> q[<span class="hljs-number">-1</span>] &lt; nums[i]:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            q.append(nums[i])
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
    
</div></code></pre>

    </body>
    </html>